home *** CD-ROM | disk | FTP | other *** search
/ Programmer Power Tools / Programmer Power Tools.iso / pcmag / vol8n07.arc / SRCHIXF.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-01-06  |  8.0 KB  |  211 lines
  1. /*
  2.     SRCHIXF.C   Searches indexed datafile previously created by MAKEIXF.EXE.
  3.     Copyright (C) 1989 Ziff Communications Co.
  4.     PC Magazine * Ray Duncan
  5.  
  6.     The user is prompted to enter a search key.  The first
  7.     8 characters of the key are used to search the sorted
  8.     index file TESTFILE.IX1 (using both sequential and binary
  9.     search algorithms) and the binary tree index file
  10.     TESTFILE.IX2.  If a match is found, the corresponding 
  11.     record number and contents from TESTFILE.DAT are displayed,
  12.     along with the number of index inspections used by each
  13.     method.
  14.  
  15.     Each record in TESTFILE.DAT is RSIZE bytes long.  The 
  16.     format of the index files is defined by the constant
  17.     KSIZE and by the structures 'index1' and 'index2'.  
  18.     All these manifest constants and structures must be kept 
  19.     synchronized with MAKEIXF.C.
  20. */
  21.  
  22. #include <stdio.h>
  23. #include <string.h>
  24. #include <stdlib.h>
  25. #include <fcntl.h>
  26. #include <sys\types.h>
  27. #include <sys\stat.h>
  28. #include <io.h>
  29.  
  30. #define RSIZE   64                      /* fixed record size */
  31. #define KSIZE    8                      /* maximum key length */
  32.  
  33. static int inspected;                   /* index entries inspected counter */
  34.  
  35. struct _index1 {                        /* sorted sequential index */
  36.       char key[KSIZE];
  37.       int recno; } ;
  38.     
  39. struct _index2 {                        /* binary tree index */
  40.       char key[KSIZE];
  41.       int recno;
  42.       int left;
  43.       int right; } ;
  44.  
  45. int binsearch(int, char *, int, int);   /* function prototypes */
  46. int seqsearch(int, char *);
  47. int treesearch(int, char *);
  48.  
  49. main()
  50. {
  51.     int i;                              /* scratch variable */
  52.     int fhdf, fhix1, fhix2;             /* file handles */
  53.     long fsize;                         /* size of file in bytes */
  54.     int frecs;                          /* number of records in file */
  55.     char key[80];                       /* key entered by user */
  56.     char rec[RSIZE];                    /* scratch record buffer */
  57.  
  58.                                         /* open all files */
  59.     fhdf  = open("TESTFILE.DAT", O_RDONLY | O_BINARY);
  60.     fhix1 = open("TESTFILE.IX1", O_RDONLY | O_BINARY);
  61.     fhix2 = open("TESTFILE.IX2", O_RDONLY | O_BINARY);
  62.  
  63.     if((fhdf == -1) || (fhix1 == -1) || (fhix2 == -1))
  64.     {
  65.         puts("\nMissing data or index file.");
  66.         exit(1);
  67.     }
  68.  
  69.     fsize = lseek(fhdf, 0L, SEEK_END);  /* find file size */
  70.     frecs = fsize / RSIZE;              /* calculate number of records */
  71.  
  72.     printf("\nTESTFILE.DAT contains %ld bytes, %d records.", fsize, frecs);
  73.  
  74.     while(1)                    
  75.     {
  76.         printf("\n\nEnter key: ");      /* prompt user and */   
  77.         gets(key);                      /* input record key */
  78.  
  79.         if(key[0] == 0) break;          /* terminate if empty line */
  80.  
  81.         if(strlen(key) > KSIZE) 
  82.             printf("\nWarning:  key truncated to %d characters.", KSIZE);
  83.  
  84.         inspected = 0;                  /* reset index entries counter */
  85.  
  86.                                         /* perform sequential search of
  87.                                            TESTFILE.IX1, display results */
  88.         printf("\nSequential search result:  ");
  89.         if((i = seqsearch(fhix1, key)) == -1) printf("record not found,");
  90.         else printf("record number is %d,", i);
  91.         printf("  %d index entries inspected.", inspected);
  92.  
  93.         inspected = 0;                  /* reset index entries counter */
  94.  
  95.                                         /* perform binary search of
  96.                                            TESTFILE.IX1, display results */
  97.         printf("\nBinary search result:      ");
  98.         if((i = binsearch(fhix1, key, 0, frecs-1)) == -1) 
  99.             printf("record not found,");
  100.         else printf("record number is %d,", i);
  101.         printf("  %d index entries inspected.", inspected);
  102.  
  103.         inspected = 0;                  /* reset index entries counter */
  104.  
  105.                                         /* perform binary tree search of
  106.                                            TESTFILE.IX2, display results */
  107.         printf("\nBinary tree result:        ");
  108.         if((i = treesearch(fhix2, key)) == -1) printf("record not found,");
  109.         else printf("record number is %d,", i);
  110.         printf("  %d index entries inspected.", inspected);
  111.  
  112.         if(i != -1)                     /* fetch record from main data */
  113.         {                               /* file and display it */
  114.             lseek(fhdf, (long) (i * RSIZE), SEEK_SET);
  115.             read(fhdf, rec, RSIZE);     
  116.             printf("\nContents of record %2d:     %s", i, rec);
  117.         }
  118.     }
  119.  
  120.     close(fhdf);                        /* release file handles */
  121.     close(fhix1);
  122.     close(fhix2);
  123. }
  124.  
  125. /*
  126.     Search index file TESTFILE.IX1 sequentially to match the 
  127.     specified key.  Called with a file handle and key address.  
  128.     Returns the record number for TESTFILE.DAT if match found, 
  129.     or -1 to indicate no match.
  130. */
  131. int seqsearch(int fh, char *kptr)
  132. {
  133.     int i;                              /* scratch variable */
  134.     struct _index1 index1;              /* receives index file data */
  135.  
  136.     lseek(fh, 0L, SEEK_SET);            /* rewind to start of file */
  137.  
  138.                                         /* do until end of file found */
  139.     while(read(fh, (char *) &index1, sizeof(index1)) != 0)
  140.     {
  141.         inspected++;                    /* inspect index entry */
  142.         i = strncmp(kptr, index1.key, KSIZE);   
  143.  
  144.         if(i == 0)                      /* if matched, return record no. */
  145.              return(index1.recno);
  146.         else if(i < 0) break;           /* if record absent, end search */
  147.     }
  148.  
  149.     return(-1);                         /* no match, return -1 */
  150. }
  151.  
  152. /*
  153.     Binary search of TESTFILE.IX1 to match the specified key.
  154.     Called with a file handle, key address, and the first 
  155.     and last record numbers of the index file segment being 
  156.     inspected.  Returns the record number for TESTFILE.DAT 
  157.     if match found, or -1 to indicate no match.
  158. */
  159. int binsearch(int fh, char *kptr, int left, int right)
  160. {
  161.     int i, j;                           /* scratch variables */
  162.     struct _index1 index1;              /* receives index file data */
  163.  
  164.     if(left > right) return(-1);        /* end search if record absent */
  165.  
  166.     i = (left + right) / 2;             /* calculate record number */
  167.                                         
  168.     inspected++;                        /* inspect index entry */
  169.     lseek(fh, (long) (i * sizeof(index1)), SEEK_SET);
  170.     read(fh, (char *) &index1, sizeof(index1));
  171.     j = strncmp(kptr, index1.key, KSIZE);
  172.  
  173.     if(j == 0) return(index1.recno);    /* if matched, return record no. */
  174.  
  175.                                         /* otherwise bisect file, recurse
  176.                                            to inspect next record */
  177.     if(j < 0) binsearch(fh, kptr, left, i-1);
  178.     else      binsearch(fh, kptr, i+1, right);
  179. }
  180.  
  181.  
  182. /*
  183.     Binary tree search of TESTFILE.IX2 to match the specified 
  184.     key.  Called with a file handle and key address.  Returns 
  185.     the record number for TESTFILE.DAT if match found, 
  186.     or -1 to indicate no match.
  187. */
  188. int treesearch(int fh, char *kptr)
  189. {
  190.     int i;                              /* scratch variable */
  191.     int node = 0;                       /* current node being inspected */
  192.     struct _index2 index2;              /* receives index file data */
  193.  
  194.     while(node != -1)                   /* do until match or empty subtree */
  195.     {
  196.         inspected++;                    /* inspect index entry */
  197.         lseek(fh, (long) (node * sizeof(index2)), SEEK_SET);
  198.         read(fh, (char *) &index2, sizeof(index2));
  199.         i = strncmp(kptr, index2.key, KSIZE);
  200.  
  201.         if(i == 0)                      /* if matched, return record no. */
  202.             return(index2.recno);
  203.  
  204.         if(i < 0)                       /* else traverse tree */
  205.              node = index2.left;
  206.         else node = index2.right;
  207.     }
  208.  
  209.     return(-1);                         /* no match, return -1 */
  210. }
  211.